class MyLinkedList {
public:
    struct ListNode{
        int val;
        ListNode *next;
        ListNode(int x):val(x), next(nullptr){}
    };

    MyLinkedList() {
        _dummyHead = new ListNode(0);   
        _size = 0;
    }
    
    int get(int index) {
        if (index < 0 || index >= _size){
            return -1;
        }
        ListNode * cur = _dummyHead->next;
        while(index--){
            cur = cur->next;
        }
        return cur->val;
    }
    
    void addAtHead(int val) {
        ListNode * head = new ListNode(val);
        head->next = _dummyHead->next;
        _dummyHead->next = head;
        _size++;
    }
    
    void addAtTail(int val) {
        ListNode * tail = new ListNode(val);
        ListNode * cur = _dummyHead; 
        for(int i=0; i<_size; i++){
            cur = cur->next;
        }
        cur->next = tail;
        _size++;
    }
    
    void addAtIndex(int index, int val) {
        if (index > _size) return;
        if (index < 0) index = 0;
        ListNode * newNode = new ListNode(val);
        ListNode * cur = _dummyHead;
        while(index--){
            cur = cur->next;
        }
        newNode->next = cur->next;
        cur->next = newNode;
        _size++;
    }
    
    void deleteAtIndex(int index) {
        if (index < 0 || index >= _size) return;
        ListNode * cur = _dummyHead;
        while(index--){
            cur = cur->next;
        }
        ListNode * tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        tmp = nullptr;
        _size--;
    }

private:
    size_t _size;
    ListNode * _dummyHead;
};

/**
    * Your MyLinkedList object will be instantiated and called as such:
    * MyLinkedList* obj = new MyLinkedList();
    * int param_1 = obj->get(index);
    * obj->addAtHead(val);
    * obj->addAtTail(val);
    * obj->addAtIndex(index,val);
    * obj->deleteAtIndex(index);
    */